package dp;

/**
 * 0-1背包问题，用动态规划方法求解
 *
 * @author zj
 */
public class KnapsackProblean {

    public static void main(String[] args) {
        int capacity = 100; //背包容量
        int value[] = {0, 20, 15, 30, 40, 25}; //价值
        int weight[] = {0, 30, 30, 25, 50, 25}; //体积
        find(value, weight, capacity);
    }

    public static void find(int value[], int weight[], int capacity) {
        int r[][] = new int[value.length][capacity + 1];
        //初始化边缘条件
        for (int i = 0; i < value.length; i++) {
            r[i][0] = 0;
        }
        for (int j = 0; j <= capacity; j++) {
            r[0][j] = 0;
        }
        for (int i = 1; i < value.length; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (weight[i] <= j) {
                    //递推表达式，是求解动态规划问题的关键
                    r[i][j] = r[i - 1][j] > (r[i - 1][j - weight[i]] + value[i]) ? r[i - 1][j]
                            : r[i - 1][j - weight[i]] + value[i];
                } else {
                    r[i][j] = r[i - 1][j];
                }
                System.out.println("r[" + i + "][" + j + "]=" + r[i][j]);
            }
        }
        System.out.println(r[value.length - 1][capacity]);
    }
}
